//#include <iostream>
//#include<string>
//using namespace std;
//
//int main() {
//    string s;
//    while (getline(cin,s)) {
//        string num;
//        auto it = s.begin();
//        auto sak = *it;
//        for (auto ch : s) {
//            if (ch == *it || sak == ' ') {
//                if (ch <= 'z' && ch >= 'a') {
//                    num.push_back(ch + 'A' - 'a');
//                }
//                else {
//                    num.push_back(ch);
//                }
//            }
//            sak = ch;
//        }
//        cout << num;
//    }
//    return 0;
//}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct Node {
    int val;
    struct Node* next;
    struct Node* random;
};

struct Node* copyRandomList(struct Node* tail) {
    if (tail == NULL)
        return NULL;
    struct Node* head = tail;
    while (head) {
        struct Node* sakura = (struct Node*)malloc(sizeof(struct Node));
        sakura->val = head->val;
        sakura->next = head->next;
        head->next = sakura;
        head = sakura->next;
    }
    head = tail;
    struct Node* up = tail->next;
    while (head) {
        if (head->random == NULL)
            up->random = NULL;
        else {
            up->random = head->random->next;
        }
        head = up->next;
        up = head->next;
    }
    head = tail;
    up = tail->next;
    struct Node* num = up;
    while (head->next) {
        up->next = head->next->next;
        head->next = up->next;
        head = head->next;
        up = up->next;
    }
    return num;
}
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return NULL;
        multiset<ListNode*> dp;
        while (head && !(dp.count(head))) {
            dp.insert(head);
            head = head->next;
        }
        return head;
    }
};